package cn.edu.anan.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序算法：
 *  1.思想：
 *      1.1.分治思想，即假如有一个数组a[p...r]需要排序
 *      1.2.可以将数组a[p...r]分解成两个子数组a[p...q]与a[q+1...r]进行排序
 *      1.3.一直分解下去，直到p>=r时，分解过程结束，且每一个分解后的子数组都有序
 *      1.4.将每次分解的两个有序子数组进行合并，得到一个合并后的有序数组
 *      1.5.最终合并结果：整个数组有序
 *  2.时间复杂度：
 *      O(nlogn)
 *  3.空间复杂度
 *      O(n)
 *  4.是否是稳定排序算法：
 *      只需要在合并阶段处理好，即为稳定排序算法
 *
 */
public class MergeSort {

    /**
     * 归并排序入口
     * @param array  待排序数组
     * @param n  数据规模
     */
    public static void sort(Integer[] array,int n){
        // 如果数据规模小于等于1，直接返回
        if(n <= 1){
            return;
        }

        // 归并排序函数
        mergeSort(array,0,n-1);
    }

    /**
     * 归并排序函数（递归实现）
     * @param array  待排序数组
     * @param left  数组起始下标
     * @param right    数组结束下标
     */
    public static void mergeSort(Integer[] array,int left,int right){
        if(left >= right){
            System.out.println("满足left>=right，退出递归：left="+left+",right="+right);
            return;
        }

        // 求解中间下标
        int mid = (left + right) / 2;
        System.out.println("当次排序：left="+left+",right="+right+",mid="+mid);

        // 分解（递归调用）
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);

        // 合并
        merge(array,left,mid+1,right);

    }

    /**
     * 合并函数
     * @param array
     * @param left
     * @param mid
     * @param right
     */
    public static void merge(Integer[] array,int left,int mid,int right){
        // 左边数组大小
        int[] leftA = new int[mid-left];
        // 右边数组大小
        int[] rightA = new int[right-mid+1];

        // 左边数组填充数据
        for(int i=left;i<mid;i++){
            leftA[i-left]=array[i];
        }

        // 右边数组填充数据
        for(int j=mid;j<=right;j++){
            rightA[j-mid]=array[j];
        }

        // 定义两个位置指针
        int L_INDEX=0,R_INDEX=0;
        // array数组第一个元素位置
        int k=left;

        // 比较两个数组的值，将小的一个放入数组array中
        while(L_INDEX<leftA.length &&
                R_INDEX<rightA.length){
            // 谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个
            if(leftA[L_INDEX] <= rightA[R_INDEX]){
                array[k++]=leftA[L_INDEX++];
            }else{
                array[k++] = rightA[R_INDEX++];
            }

        }

        // 如果左边的数组有剩余元素
        while(L_INDEX<leftA.length){
            array[k++] = leftA[L_INDEX++];

        }

        // 如果右边的数组有剩余元素
        while(R_INDEX<rightA.length){
            array[k++] = rightA[R_INDEX++];
        }
    }

}
